package binary_tree.LeetCode;
/**
 * 判断是否为平衡二叉树，在二叉树中每个节点的左右高度差<=1
 */
public class Num110 {

    public boolean isBalanced(TreeNode root) {
      if (root==null){
          return true;
      }
      //求左子树的高度
        int left=rootHeight(root.left);
      //求右子树的高度
        int right=rootHeight(root.right);
        int num=Math.abs(left-right);
        //判断是否为平衡二叉树，在二叉树中每个节点的左右高度差<=1
        return num<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }

    /**
     * 传入二叉树的根节点，就可以知道树的高度
     * @param root
     * @return
     */
    public int rootHeight(TreeNode root){
        if (root==null) {
            return 0;
        }
        //二叉树的高度=1+（左子树高度和右子树高度的最大值）
        return 1+Math.max(rootHeight(root.left),rootHeight(root.right));
    }

}
